﻿P1677[USACO18FEB] Hoofball B



为了准备即将到来的蹄球锦标赛，Farmer John 正在训练他的 N 头奶牛（方便起见，编号为 1…N，其中 1≤N≤100）进行传球。这些奶牛在牛棚一侧沿直线排列，第 i 号奶牛位于距离牛棚 x
i
​
的地方（1≤x
i
​
≤1000）。每头奶牛都在不同的位置上。

在训练开始的时候，Farmer John 会将若干个球传给不同的奶牛。当第 i 号奶牛接到球时，无论是从 Farmer John 或是从另一头奶牛传来的，她会将球传给最近的奶牛（如果有多头奶牛与她距离相同，她会传给其中距左边最远的那头奶牛）。为了使所有奶牛都有机会练习到传球，Farmer John 想要确保每头奶牛都持球至少一次。帮助他求出为了达到这一目的他开始时至少要传出的球的数量。假设他在开始的时候能将球传给最适当的一组奶牛。

输入格式
输入的第一行包含 N。第二行包含 N 个用空格分隔的整数，其中第 i 个整数为 x
i
​
。

输出格式
输出 Farmer John 开始的时候最少需要传出的球的数量，使得所有奶牛至少持球一次。

输入输出样例
输入 #1复制

5
7 1 3 11 4
输出 #1复制

2
说明 / 提示
在上面的样例中，Farmer John 应该将球传给位于 x = 1 的奶牛和位于 x = 11 的奶牛。位于 x = 1 的奶牛会将她的球传给位于 x = 3 的奶牛，在此之后这个球会在位于 x = 3 的奶牛和位于 x = 4 的奶牛之间来回传递。位于 x = 11 的奶牛会将她的球传给位于 x = 7 的奶牛，然后球会被传给位于 x = 4 的奶牛，在此之后这个球也会在位于 x = 3 的奶牛和位于 x = 4 的奶牛之间来回传递。这样的话，所有的奶牛都会至少一次接到球（可能从 Farmer John，也可能从另一头奶牛）。

可以看出，不存在这样一头奶牛，Farmer John 可以将球传给她之后所有奶牛最终都能被传到球。







//思路：涉及到传球的时候的距离最近问题，因此可以先排序，这样就变成了传左还是右的问题，其次就是每个奶牛都可以传出去，但不一定能收到球
//因此可以记录下它传给谁，以及它收到几个球（这里不用记录谁给他的） ，还要知道每个奶牛只能固定传给一个奶牛，但是可以收到不同奶牛传给的球其次就是分两种情况：
//1·能走一连串，也就是总是出现一个牛cnt为0，因此只需要传给它球，就完成了 任务 ！
//2·分段，此时是多组 多组的 也就是大于2个，此时又会转化成多种情况一（cnt又会出现为0的一个）；还有一种是两两一段，此时cnt 
//都为1，因此这种两两进行的循环，必须一开始传一个 ！ 
#include<bits/stdc++.h>
using namespace std;
int arr[105];//奶牛距离牛棚的距离
int n;
int next1[105];//next[i]=j:i号奶牛下一个把求传给j
int cnt[105];//i号奶牛可以收到了几个球
int ans;//记录答案 
void greedy_solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    stable_sort(arr + 1, arr + n + 1);
    arr[0] = -0x3f3f3f3f;//边界特判 
    arr[n + 1] = 0x3f3f3f3f;//边界特判 
    for (int i = 1; i <= n; i++) {
        if (arr[i] - arr[i - 1] > arr[i + 1] - arr[i]) {
            next1[i] = i + 1;
            cnt[i + 1]++;
        }
        else {
            next1[i] = i - 1;//这里应该是如果距离都相等 ，传给距离牛棚最近的，代码才这么写 
            cnt[i - 1]++;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (cnt[i] == 0) ans++;//统计唯一的cnt为0 
        else if (cnt[i] == 1 && cnt[i + 1] == 1 && next1[i] == i + 1 && next1[i + 1] == i) ans++;//统计两两死循环传递的 
    }
    cout << ans << endl;
}
int main() {
    greedy_solve();
    return 0;
}